#include "Rabin_Karp.hpp"


/**
 * @brief Construct a new Rabin_Karp_Matcher::Rabin_Karp_Matcher object
 * 
 * @param T 被匹配的字符串
 * @param P 模式字符串
 */
Rabin_Karp_Matcher::Rabin_Karp_Matcher(string T, string P, int d, int q){
    this->P_length = P.length();
    this->T_length = T.length();
    this->P = "x" + P;
    this->T = "x" + T;
    this->d = d;
    this->q = q;
}


/**
 * @brief 比较从s+1开始的T串和从1开始的P串是否相同
 * 
 * @param s 起始下标-1
 * @return true 相同
 * @return false 不相同
 */
bool Rabin_Karp_Matcher::cmp(int s){
    for (size_t i = 1; i <= P_length; i++)
    {
        if (P[i] != T[s+i])
        {
            return false;
        }
        
    }
    return true;
}


/**
 * @brief 运行Rabin-Karp算法
 * 
 * @return vector<int> 第一项：命中次数；第二项：伪命中次数
 */
vector<int> Rabin_Karp_Matcher::run_Matcher(){
    vector<int> ret = {0, 0};
    auto n = this->T_length;
    auto m = this->P_length;
    int h = 1;
    for (size_t i = 0; i < m-1; i++)
    {
        h *= d;
        h = h % q;
    }
    int p = 0, t = 0;
    for (size_t i = 1; i <= m; i++)
    {
        p = (d*p + P[i]) % q;
        t = (d*t + T[i]) % q;
    }
    for (size_t s = 0; s <= n - m; s++)
    {
        if (p == t)
        {
            if (this->cmp(s))
            {
                cout << "Pattern occurs with shift " << s << endl;
                ret[0] ++;
            }
            else ret[1] ++;
        }
        if (s < n - m)
        {
            t = ((d*(t - T[s+1]*h) + T[s+m+1]) % q + q) % q;
        }
    }
    return ret;
}